package main.java.Fzy.Work.task01;

public class Demo2 {

    public static void main(String[] args) {
        MyHashTable<Integer,String> myHashTable = new MyHashTable<>();

        myHashTable.put(1,"123");
        myHashTable.put(2,"234");
        myHashTable.put(3,"345");
        System.out.println("查找2号");
        System.out.println(myHashTable.get(2));
        System.out.println("删除2号");
        myHashTable.remove(2);
        System.out.println("删除后："+myHashTable.get(2));

    }
}

/**
* @author LazyCat
* @date  2022/11/19
* @param
* @return
 * 哈希表对象
*/
class MyHashTable<K,T>{
    //核心存储数组
    private MyLinkedList<K,T>[] map = new MyLinkedList[16];
    //初始化数组大小
    private static final int INT_SIZE = 16;
    //数组扩展倍数
    private static final double EXPAND = 1.5;
    //扩展阈值
    private static final double THRESHOLD = 0.8;
    //链表的结点数目  -----> 还可用于转换红黑树
    private int nodeNums = 0;
    //数组元素的占用数目
    private int arrayNums = 0;
    //初始数组的大小
    private int arraySizeMax = INT_SIZE;

    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 创建元素管理节点
    */
    private MyLinkedList<K,T> generateMyList(K key,T data){
        MyLinkedList<K,T> linkedList = new MyLinkedList<>();
        linkedList.put(key,data);
        return linkedList;
    }
    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 是否达到扩展要求
    */
    public boolean IsExpand(){
        return arraySizeMax*THRESHOLD <= (double) arrayNums;
    }

    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 扩展
    */
    private void expand(){
        if (!IsExpand()) {
            return;
        }
        int length = (int) (this.arraySizeMax*MyHashTable.EXPAND);
        this.arraySizeMax = length;
        MyLinkedList<K,T>[] newMap = new MyLinkedList[length];
        for(MyLinkedList<K,T> list : map){
            if(list != null){
                int index = (list.getNode().hashCode() * arraySizeMax) % arraySizeMax;
                newMap[index] = list;
            }
        }
        this.map = newMap;
        System.gc();
    }

    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 查找数据
    */
    public T get(K key){
        int index = key.hashCode()/arraySizeMax%arraySizeMax;
        if(map[index]==null){
            return null;
        }else {
            return map[index].get(key);
        }
    }
    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 删除数据
    */
    public T remove(K key){
        int index = key.hashCode()/arraySizeMax%arraySizeMax;
        if(map[index] == null){
            return null;
        }else {
            T remove = map[index].remove(key);
            if(remove!=null){
                nodeNums--;
            }
            return remove;
        }
    }

    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 添加数据
    */
    public void put(K key,T data){
        if (IsExpand()) {
            expand();
        }
        int index = key.hashCode()/arraySizeMax%arraySizeMax;
        //判断当前结点是否存在数据
        if(map[index]!=null && map[index].isEmpty()){
            map[index].put(key,data);
        }else if(map[index] == null){
            MyLinkedList<K,T> myLinkedList = generateMyList(key, data);
            map[index] = myLinkedList;
            arrayNums++;
        }else {
            map[index].put(key, data);
        }
        nodeNums++;
    }
}


/**
* @author LazyCat
* @date  2022/11/19
* @param
* @return
 * 结点管理
*/
class MyLinkedList<K,T>{
    //定义头尾结点
    private MyObjectNode<K,T> node = null;
    private MyObjectNode<K,T> nodeEnd = null;

    private int elementNums = 0;

    public int getElementNums(){
        return elementNums;
    }

    public boolean isEmpty(){
        return elementNums == 0;
    }

    public MyObjectNode<K, T> getNode() {
        return node;
    }

    public void setNode(MyObjectNode<K, T> node) {
        this.node = node;
    }

    public MyObjectNode<K, T> getNodeEnd() {
        return nodeEnd;
    }

    public void setNodeEnd(MyObjectNode<K, T> nodeEnd) {
        this.nodeEnd = nodeEnd;
    }

    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param key 查找key值
    * @return T 返回查找的值
     * 获取指定元素结点
    */
    public T get(K key){
        if (isEmpty()) {
            return null;
        }
        MyObjectNode<K,T> temp = this.node;
        while (temp != null){
            if(temp.getKey().equals(key)){
                return temp.getData();
            }
            temp = temp.getNext();
        }
        return null;
    }
    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param key 添加键值
     * @param data 添加值
    * @return
     * 添加节点
    */
    public void put(K key,T data){
        if (isEmpty()) {
            this.node = new MyObjectNode<>(key,data);
            this.node.setPre(this.node);
            nodeEnd = node;
            elementNums++;
            return;
        }
        //判断是否key重合
        MyObjectNode<K,T> cur = this.node;
        while (cur != null){
            if(cur.getKey().equals(key)){
                cur.setData(data);
                return;
            }
            cur = cur.getNext();
        }
        //没有重合
        MyObjectNode<K,T> newNode = new MyObjectNode<>(key, data);
        newNode.setPre(nodeEnd);
        nodeEnd.setNext(newNode);
        nodeEnd = newNode;
        elementNums++;
    }
    /**
    * @author LazyCat
    * @date  2022/11/19
    * @param
    * @return
     * 删除结点
    */
    public T remove(K key){
        if(elementNums == 1){
            T data = this.node.getData();
            this.node = null;
            nodeEnd = null;
            elementNums = 0;
            return data;
        }
        MyObjectNode<K,T> cur = this.node;
        while (cur != null){
            if(cur.getKey().equals(key)){
                if(cur == nodeEnd){
                    T data = cur.getData();
                    cur.getPre().setNext(null);
                    nodeEnd = cur.getPre();
                    return data;
                }
                //找到元素并删除
                MyObjectNode<K,T> pre = cur.getPre();
                MyObjectNode<K,T> next = cur.getNext();
                if(pre != null){
                    pre.setNext(next);
                }
                if (next != null) {
                    next.setPre(pre);
                }
                elementNums--;
                return cur.getData();
            }
            cur = cur.getNext();
        }
        return null;
    }
}

/**
* @author LazyCat
* @date  2022/11/19
* @param
* @return
 * 节点类 ---> 双向链表
*/
class MyObjectNode<K,T>{

    private K key;
    private MyObjectNode<K,T> pre;
    private MyObjectNode<K,T> next;
    private T data;

    public MyObjectNode(K key,T data){
        this.key = key;
        this.data = data;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public MyObjectNode<K, T> getPre() {
        return pre;
    }

    public void setPre(MyObjectNode<K, T> pre) {
        this.pre = pre;
    }

    public MyObjectNode<K, T> getNext() {
        return next;
    }

    public void setNext(MyObjectNode<K, T> next) {
        this.next = next;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}